package com.gxc.tree;

import java.util.Stack;

/**
 * 树的先序遍历
 */
public class Preorder {

    public static void main(String[] args) {
        TreeBean tree = createTree();

        //递归实现先序遍历
        recursion(tree);

        System.out.println("----------");
        Stack<TreeBean> stack = new Stack<>();
        stack.push(tree);
        nonRecursion(stack);
    }

    /**
     * 非递归实现先序遍历
     * @param stack
     */
    private static void nonRecursion(Stack<TreeBean> stack) {
        while (!stack.empty()) {
            TreeBean treeBean = stack.pop();
            System.out.print(treeBean.value + "  ");
            if (treeBean.right!=null) stack.push(treeBean.right);
            if (treeBean.left!=null) stack.push(treeBean.left);
        }
    }

    /**
     * 递归实现先序遍历
     * @param tree
     */
    private static void recursion(TreeBean tree) {
        if (tree == null) return;

        System.out.print(tree.value + "  ");
        recursion(tree.left);
        recursion(tree.right);
    }

    /**
     * 创建普通树
     * @return
     */
    public static TreeBean createTree() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;

        three.left = six;
        three.right = seven;

        four.left = eight;
        return one;
    }

    /**
     * 创建搜索树
     * @return
     */
    public static TreeBean createSearchBinaryTrees() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        five.left = three;
        five.right = seven;

        three.left = two;
        three.right = four;

        seven.left = six;
        seven.right = eight;

        two.left = one;
        return five;
    }

    /**
     * 创建完全二叉树   除了最后一层玩，其他层节点满，且最后一层有右节点的必有左节点
     * @return
     */
    public static TreeBean createNoCompleteBinaryTree() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        five.left = three;
        five.right = seven;

        three.left = two;
        three.right = four;

        seven.left = six;

        two.left = one;
        return five;
    }

    /**
     * 创建满二叉树
     * @return
     */
    public static TreeBean createFullBinaryTree() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);

        five.left = three;
        five.right = seven;

        three.left = two;
        three.right = four;

        seven.left = six;
        seven.right = one;

        return five;
    }

    /**
     * 创建非平衡二叉树
     * @return
     */
    public static TreeBean createNoBalancedBinaryTree() {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;

        four.left = six;
        four.right = seven;

        six.left = eight;
        return one;
    }
}
